import java.nio.charset.MalformedInputException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-31
 * Time: 20:04
 */
public class Solution {

    // 二分查找
    public int minDays(int[] bloomDay, int m, int k) {
        int max = bloomDay[0];
        int len = bloomDay.length;
        if (m * k > len) {
            return -1;
        }
        for (int i = 0; i < len; i++) {
            max = Math.max(max, bloomDay[i]);
        }
        int left = 1;
        int right = max + 1; // right 多取 1 方便后面判断到底 left 是否符合条件
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            int count = 0;
            for (int i = 0; i < len;) {
                if (bloomDay[i] <= mid) {
                    int constant = 0;
                    while (i < len && bloomDay[i] <= mid && constant < k) {
                        constant++;
                        i++;
                    }
                    if (constant == k) {
                        // 连续 k 朵
                        count++;
                        // 连续 k 朵之后 i 因为已经提前 +1 了, 所以 i 不用再加了
                    } else {
                        // 因为越界或者 花还没有开 这种条件 i 可以再 + 1
                        i++;
                    }
                } else {
                    // 不满足条件直接 +1
                    i++;
                }
            }
            if (count < m) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 因为 最终 left == right, 所以最终无法知道 left 到底是满足不满足条件
        // 所以 right 多取 1, 最终 left 与 max 进行比较就可以得出到底是否满足条件了
        return left > max ? -1 : left;
    }
}
